package summary;

import java.util.PriorityQueue;

/**
 * @Author: 海琳琦
 * @Date: 2022/6/8 20:41
 * https://leetcode.cn/problems/the-k-weakest-rows-in-a-matrix/
 */
public class Title1337 {

    public static int[] kWeakestRows(int[][] mat, int k) {
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> {
            if (a[0] == b[0]) {
                return a[1] - b[1];
            }else {
                return a[0] - b[0];
            }
        });
        int n = mat.length;
        for (int i = 0; i < n; i++) {
            //二分查找1的位置
            int left = 0, right = mat[i].length - 1;
            int pos = -1;
            while (left <= right) {
                int middle = (left + right) / 2;
                if (mat[i][middle] == 1 ) {
                    pos = middle;
                    left = middle + 1;
                }else{
                    right = middle - 1;
                }
            }
            queue.offer(new int[]{pos + 1, i});
        }
        int[] result = new int[k];
        int count = 0;
        while (queue.size() > n - k) {
            result[count++] = queue.poll()[1];
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] arr = {{1, 1, 0, 0, 0},
                {1, 1, 1, 1, 0},
                {1, 0, 0, 0, 0},
                {1, 1, 0, 0, 0},
                {1, 1, 1, 1, 1}};
        int k = 3;
        kWeakestRows(arr, 3);
    }
}
